7.1 哈希函数与哈希表
哈希函数和哈希表是数据结构中的重要概念，广泛应用于查找、存储和管理数据，尤其是在实现高效的数据访问时。
本节我们将介绍哈希函数和哈希表的基本概念、应用场景，并展示如何在Go语言中实现一个简单的哈希表。
本节代码存放目录为 lesson15
概念与原理
哈希表
哈希表（Hash Table）是一种用于快速查找数据的表结构。哈希表可以在常数时间复杂度 O(1) 内完成查找、插入和删除操作。
哈希表的基本结构：
键（Key）：用于唯一标识数据的值。
值（Value）：与键相关联的数据。
哈希表的工作原理：
输入键，通过哈希函数计算出一个哈希值。
根据哈希值（索引）找到对应的存储位置。
将数据存储在该位置，或在查找时直接访问该位置的数据。
结构示意如下所示：
索引 0 1 2 3 4 5 6 7 8 9
存储 - - - - - A B - - -
在上面的示意中，A 被映射到了索引 5 的位置上，B 被映射到了索引 6 的位置上。
所以我们可以总结为这样：根据key计算得到一个索引，之后将value存储到了数组对应索引的位置。
比如我们举个最简单的例子，我们现在有这样的键值对：
0: A
1: B
3: C
4: D
5: E
那么此时我们就可以直接将 key 作为数组索引直接存储：
索引 0 1 2 3 4 5 6 7 8 9
存储 A B C D E - - - - -
所以我们可以将哈希表的底层理解为是一个数组，通过 key 计算出索引，之后将 value 进行对应存储。
哈希函数
哈希函数是一种将任意长度的输入数据映射到固定长度输出的函数。其核心目标是通过将数据转化为一个哈希值来确定其存储位置。
我们可以理解为，哈希函数就是为了计算出上文中我们提到的数组索引，这个索引决定了数据存储在数组的哪个位置。
哈希函数作用如下：
输入：任意长度的字符串、整数等数据类型。
输出：一个定长的整数（哈希值），用于表示该数据的存储位置。
哈希函数的特点：
确定性：相同的输入总会得到相同的哈希值。
高效性：计算哈希值应该是快速的。
均匀分布：理想情况下，哈希值应该均匀分布，以避免
碰撞。
那么什么是碰撞呢？
当两个不同的输入通过哈希函数得到相同的哈希值时，称为碰撞。由于哈希值的范围是有限的，碰撞是不可避免的。
我们可以理解为不同的输入 A、B 通过哈希函数计算后，输出的存储索引都为 0，那么这时候就会出现冲突，也就是碰撞。
解决碰撞的常见策略如下所示：
链地址法：将具有相同哈希值的元素存储在同一个链表中。
开放寻址法：在发生碰撞时，寻找下一个空闲的位置存储元素。
解决哈希碰撞也是经常需要遇到的，在下一节我们将针对链地址法、开放寻址法进行详细的讲解。
哈希函数示例
我们以一个简单的示例说明：
11: A
12: B
13: C
14: D
15: E
当前哈希表初始结构如下：
索引 0 1 2 3 4 5 6 7 8 9
存储 - - - - - - - - - -
哈希函数如下：
func hash(key int) int {
h := key
return h % 10
}
在上面的代码中，我们直接将 key 作为哈希值，之后进行了取余运算，10代表的是底层数组的长度。
那么 key 11 计算得出的就是：1，其他计算得出的是这样：
11: 1
12: 2
13: 3
14: 4
15: 5
通过上面的示例我们可以看出，哈希函数主要做的就是两件事情，第一是计算哈希值，第二就是进行取模运算，或者说取余运算，得出最终的索引。
哈希表的常见应用如下：
数据查找：哈希表能快速找到特定元素。
缓存系统：哈希表可以用于实现缓存，通过键快速找到对应的数据。
集合操作：哈希表能高效地管理集合中的元素，支持插入、删除、查找操作。
Go语言的实现
我们将使用Go语言实现一个简单的哈希表，其中每个哈希值的位置存储一个链表，解决碰撞问题。
// Entry 定义键值对结构
type Entry struct {
key string
value string
next *Entry
}
// HashTable 定义哈希表结构
type HashTable struct {
table []*Entry
size int
}
// NewHashTable 创建一个哈希表
func NewHashTable(size int) *HashTable {
return &HashTable{
table: make([]*Entry, size),
size: size,
}
}
// Hash 函数计算哈希值
func (h *HashTable) Hash(key string) int {
hash := 0
for _, char := range key {
hash += int(char)
}
return hash % h.size
}
// Put 插入键值对到哈希表
func (h *HashTable) Put(key string, value string) {
index := h.Hash(key)
entry := h.table[index]
// 如果该位置为空，直接插入
if entry == nil {
h.table[index] = &Entry{key: key, value: value}
return
}
// 解决碰撞，检查链表中是否已经存在该键
for entry != nil {
if entry.key == key {
entry.value = value // 更新值
return
}
if entry.next == nil {
break
}
entry = entry.next
}
// 将新的键值对插入链表末尾
entry.next = &Entry{key: key, value: value}
}
// Get 根据键查找值
func (h *HashTable) Get(key string) (string, bool) {
index := h.Hash(key)
entry := h.table[index]
for entry != nil {
if entry.key == key {
return entry.value, true
}
entry = entry.next
}
return "", false
}
// Remove 删除键值对
func (h *HashTable) Remove(key string) {
index := h.Hash(key)
entry := h.table[index]
if entry == nil {
return
}
// 如果第一个元素就是要删除的键
if entry.key == key {
h.table[index] = entry.next
return
}
// 遍历链表寻找要删除的键
prev := entry
entry = entry.next
for entry != nil {
if entry.key == key {
prev.next = entry.next
return
}
prev = entry
entry = entry.next
}
}
func main() {
// 创建哈希表
hashTable := NewHashTable(10)
// 插入键值对
hashTable.Put("A", "Apple")
hashTable.Put("B", "Banana")
hashTable.Put("C", "Cherry")
// 查找键值对
value, found := hashTable.Get("B")
if found {
fmt.Println("Key B:", value)
} else {
fmt.Println("Key B not found")
}
// 删除键值对
hashTable.Remove("B")
fmt.Println("remove B")
value, found = hashTable.Get("B")
if found {
fmt.Println("Key B:", value)
} else {
fmt.Println("Key B not found")
}
}
执行结果如下所示：
Key B: Banana
remove B
Key B not found
小结
本节我们讲解了哈希表的基本概念、哈希函数的概念及作用，同时我们通过Go语言实现了简单的哈希表。
关于本节总结如下：
哈希表是一种常见的数据结构，能够在
O(1)时间内高效地进行插入、查找和删除。哈希函数通过将键映射为哈希值，确保快速的查找和插入操作。
在
Go语言中，可以通过链表解决哈希碰撞问题，实现哈希表的高效操作。